package com.aqie.medium.doublePointer;

import java.util.Arrays;

/**
 * 16 最接近的三数之和 todo
 */
public class ThreeSumClosest {
    /**
     * 1, 17ms
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }


    /**
     * 2，双指针对撞 14ms
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest2(int[] nums, int target) {
        int len = nums.length;
        // 特判
        if (len < 3) {
            throw new IllegalArgumentException("参数错误");
        }
        // 初始化，因为找最小值，因此把初始值设置成实数的最大值
        int diff = Integer.MAX_VALUE;
        int res = nums[0] + nums[1] + nums[len - 1];
        // 排序是前提，很关键
        Arrays.sort(nums);
        // len-3 len-2 len-1

        for (int i = 0; i < len - 2; i++) {
            // 常见的剪枝操作
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 双指针：指针对撞
            int left = i + 1;
            int right = len - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                // 不管是变小还是变大，尝试的作用是让 sum 与 target 更接近
                // 即 s 与 target 的绝对值之差越来越小
                if (sum > target) {
                    // 如果大了，尝试右边界收缩一格，让 target 变小
                    right--;
                } else if (sum < target) {
                    // 如果小了，尝试左边界收缩一格，让 target 变大
                    left++;
                } else {
                    // 如果已经等于 target 的话, 肯定是最接近的，根据题目要求，返回这三个数的和
                    assert sum == target;
                    return target;
                }

                if (Math.abs(sum - target) < diff) {
                    diff = Math.abs(sum - target);
                    res = sum;
                }
            }
        }
        return res;
    }


    /**
     * 3, 12ms
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest3(int[] nums, int target) {
        int ans = 0x3f3f3f3f;
        // 排序，正常操作
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                // 如果当前target指向的值与前一个相同，说明这个值以及被计算过了，
                // 为了避免冗余，直接跳过
                continue;
            }

            int ans_temp = TwoSum(nums,i + 1, nums.length - 1, i, target);
            // 更新结果，用更小差值的和来更新
            if(Math.abs(target - ans) > Math.abs(target - ans_temp)){
                ans = ans_temp;
            }
        }
        return ans;
    }

    private int TwoSum(int[] nums, int begin, int end, int cur, int target){
        // 定义最终返回的解
        // 设定为一个很大的值
        int difference = 0x3f3f3f3f;
        int ans = 0x3f3f3f3f;
        int left = begin;
        int right = end;
        int target_num = target - nums[cur];

        // 正式的找解的过程
        while(left < right){
            // 定义一个临时变量，用于记录当前左右指针指向的数的和与target_num之间的差值。
            // 注意，这里的target_num不等于题目的target，是自己定义的一个临时变量，用于将问题转化为 Two Sum Closet 问题
            int temp_dif = nums[left] + nums[right] - target_num;

            // 发现这个差值比前面一次的差值要小，则更新返回的和，以及差值
            // 这里比较差值用了绝对值，因为只有绝对值小才是真的差异小。

            if(Math.abs(temp_dif) < difference){
                ans = nums[left] + nums[right] + nums[cur];
                difference = Math.abs(temp_dif);
            }

            // 这里更新左右指针，试图寻找到一个和target_num差值较小的数
            // 这里没有利用绝对值，是为了利用差值的正负性来更新指针的移动方向
            // 有点梯度下降的味道
            if(temp_dif > 0){
                // 和过大，因此右指针左移
                right--;
            }else if(temp_dif < 0){
                // 和过小，因此左指针右移
                left++;
            }else {
                // 找到了一个恰好等于target的组合，差值为0.可以直接返回
                break;
            }
        }
        return ans;
    }

}
